home *** CD-ROM | disk | FTP | other *** search
/ The Fatted Calf / The Fatted Calf.iso / Applications / Graphics / GraphicsWrap / Source / NXBitmapGraphicRep.m < prev    next >
Text File  |  1991-09-18  |  21KB  |  757 lines
  1. /* -------------------------------------------------------------------
  2.                           NXBitmapGraphicRep                     
  3.         1. Definition
  4.        This class is designed to simply and effeciently implement
  5.        simple bitmap graphics operations and provide a method to
  6.        get them on the screen quickly.
  7.  
  8.        Advanced bitmap stuff (lines, circles, polygon fills, etc.)
  9.        are left as an exercise for the programmer.
  10.  
  11.     2. Usage
  12.     bitmap characteristics:
  13.       - initialization
  14.         initWithSize: aSize depth:aDepth andColor:aColor
  15.         initializes the bitmap and allocates image data for an
  16. image with a size of aSize, a pixel depth of aDepth and clears the
  17. background to aColor.
  18.         initWithSize: depth:
  19.             same as above, but initializes background to black.
  20.  
  21.       - drawing:
  22.         plotPoint:x :y;
  23.         erasePoint:x :y;
  24.     plots a point in the current foreColor
  25.     erases a point to the current backColor
  26.  
  27.     the rest of the methods are fairly self explanatory (and are
  28. mostly documented within themselves.
  29.  
  30.     3. Theory
  31.   When the bitmap is initialized, it's superclass allocates enough
  32. data to hold an entire image at the initialized depth.  The image data
  33. is stored in an array of unsigned char's.  The array is arranged
  34. thusly:
  35.                samp1=red, samp2=green, samp3=blu. 
  36.  
  37. 24 bit color:  8 bits/sample, 3 samples/pixel, 3 bytes/pixel
  38. [      pixel1       ][      pixel2       ]...
  39. [samp1][samp2][samp3][samp1][samp2][samp3]...
  40.  
  41. 12 bit color:  4 bits/sample, 3 samples/pixel, 1.5(!) bytes/pixel
  42.  
  43. [      pixel1       ][      pixel2       ][      pixel1       ]...
  44. [samp1][samp2][samp3][samp1][samp2][samp3][samp1][samp2][samp3]...
  45. [   data[0]  ][   data[1]  ][   data[2]  ][   data[3]  ][   data[4]  ]...
  46.  
  47. 2 bit gray scale: 2 bits/pixel, 4 pixels/byte
  48. [pix1][pix2][pix3][pix4][pix5][pix6][pix7][pix8]...
  49. [       data[0]        ][       data[1]        ]...
  50. NOTE: pix1 is in bits 7&8
  51.       pix2 is in bits 5&6
  52.       pix3 is in bits 3&4
  53.       pix4 is in bits 1&2 etc...
  54.  
  55. Because of this arrangement, both plotPoint and erasePoint use bit
  56. manipulation to deal with 12 bit and 2 bit color models.
  57.  
  58. Because of this, Color management is a bit strange:
  59. Internally, all colors are represented as NXColor structures:  this
  60. gives full support for CMYK, RGB, and HSB color models (just make sure
  61. and use NeXT's color conversion routines).  
  62.  
  63. The colors are ALSO stored in an optimal form for doing bit level
  64. pixel manipulation:
  65.  
  66. 24 bit: cur_red, cur_grn, cur_blu all contain a full 8 bit byte with
  67. the RGB intensity level for the corresponding color (0 is off, 255 is
  68. full-on)
  69.  
  70. 12 bit: same as 24 bit, but the bottom four bits are masked off.
  71. Effectively giving 16 levels of color for each channel (4096 colors).
  72.  
  73. 2 bit: gray_level contains the top 2 bits of the color level that has
  74. been converted to a gray level.
  75.  
  76. By doing this, it ensures maximum throughput while avoiding any of
  77. postscripts dithering muck.  Also, since internally, colors are
  78. represented in the full NXColor way, you DO NOT lose color informaton
  79. even if you are plotting in 2 bit gray-- as soon as you switch to a
  80. deeper color model, this object will take advantage of it.
  81.  
  82. This object is designed to be hacked.  There are some fairly obvious
  83. optimizations that could be done when implementing line-drawing or
  84. poly-fills.
  85.  
  86. Remember:  bcopy(src, dest, #bytes) is a hell of a lot faster than a
  87. fore-loop that does the same thing (check out the eraseFrame method).
  88. ------------------------------------------------------------------- */
  89. #import "NXBitmapGraphicRep.h"
  90.  
  91. #import <appkit/color.h>
  92. #import <appkit/graphics.h>
  93. #import <string.h>
  94. #import <stdio.h>
  95. #import <math.h>
  96. #import <c.h>
  97. #import "miscutil.h"
  98.  
  99. #import "CmdVertex.h"
  100. #import "CmdBgnpoly.h"
  101. #import "CmdEndpoly.h"
  102.  
  103. extern void exit();
  104. extern void *malloc();
  105. extern void free();
  106. @implementation NXBitmapGraphicRep : NXBitmapImageRep
  107.  
  108. #define RED24 0
  109. #define GRN24 1
  110. #define BLU24 2
  111.  
  112. // macro to convert x,y coordinates to offset from byte 0 of the data array
  113. #define xyto24index(x,y) (((yh-y)*bytes_per_row)+(x*3))
  114. #define xyto12index(x,y) (((yh-y)*bytes_per_row)+((3*x)/2))
  115. #define xyto2index(x,y)  (((yh-y)*bytes_per_row)+(x/4))
  116.  
  117. - initBitmap
  118. {
  119.   int i;
  120.   unsigned char *top_line;
  121.  
  122.   bytes_per_row=[self bytesPerRow];
  123.   num_bytes=[self pixelsHigh]*bytes_per_row;
  124.   data=[self data];
  125.  
  126.   yh=[self pixelsHigh]-1;
  127.  
  128.   // erase first line to back color
  129.   for(i=0;i<[self pixelsWide];i++)
  130.     [self erasePoint:i:0];
  131.   
  132.   switch(imageDepth){
  133.   case NX_TwoBitGrayDepth:
  134.     top_line=&data[xyto2index(0,0)];
  135.     for(i=0;i<[self pixelsHigh];i++)
  136.       bcopy(top_line, &(data[xyto2index(0,i)]), bytes_per_row);
  137.     break;
  138.   case NX_TwelveBitRGBDepth:
  139.     top_line=&data[xyto12index(0,0)];
  140.     for(i=0;i<[self pixelsHigh];i++)
  141.       bcopy(top_line, &(data[xyto12index(0,i)]), bytes_per_row);
  142.     break;
  143.   case NX_TwentyFourBitRGBDepth:
  144.     top_line=&data[xyto24index(0,0)];
  145.     for(i=0;i<[self pixelsHigh];i++)
  146.       bcopy(top_line, &(data[xyto24index(0,i)]), bytes_per_row);
  147.     break;
  148.   }
  149.   return self;
  150. }
  151.  
  152. //    NX_DefaultDepth = 0,
  153. //    NX_TwoBitGrayDepth = 258,
  154. //    NX_EightBitGrayDepth = 264,
  155. //    NX_TwelveBitRGBDepth = 516,
  156. //    NX_TwentyFourBitRGBDepth = 520
  157. - initWithSize:(NXSize *) aSize depth:(int) aDepth andColor:(NXColor)c;
  158. {
  159.   imageDepth=aDepth;
  160.   [self setBackColor:c];
  161.   switch(aDepth) {
  162.   case NX_TwoBitGrayDepth:
  163.     // this will yield a bitmap w/4 pixels per byte at 2 bits per pixel.
  164.     [super initData:NULL     
  165.      pixelsWide:aSize->width 
  166.      pixelsHigh:aSize->height
  167.      bitsPerSample:2       
  168.      samplesPerPixel:1     
  169.      hasAlpha:NO             
  170.      isPlanar:NO               
  171.      colorSpace:NX_OneIsWhiteColorSpace
  172.      bytesPerRow:0         
  173.      bitsPerPixel:0];
  174.     break;
  175.   case NX_TwelveBitRGBDepth:
  176.     // this will yield a bitmap w/4 bits per sample and 3 samples per pixel.
  177.     [super initData:NULL     
  178.      pixelsWide:aSize->width 
  179.      pixelsHigh:aSize->height
  180.      bitsPerSample:4
  181.      samplesPerPixel:3
  182.      hasAlpha:NO             
  183.      isPlanar:NO               
  184.      colorSpace:NX_RGBColorSpace
  185.      bytesPerRow:0         
  186.      bitsPerPixel:0];
  187.     break;
  188.   case NX_TwentyFourBitRGBDepth:
  189.     [super initData:NULL            // force NXBitmapImageRep to allocate data
  190.      pixelsWide:aSize->width        // set the width
  191.      pixelsHigh:aSize->height       // set the height
  192.      bitsPerSample:8                // set the # of bits per sample
  193.      samplesPerPixel:3              // set the # of samples per pixel
  194.      hasAlpha:NO                    // Do not want alpha channel
  195.      isPlanar:NO                    // Data should be interleaved in one array
  196.      colorSpace:NX_RGBColorSpace    // standard RGB color space
  197.      bytesPerRow:0                  // allocate the data automatically
  198.      bitsPerPixel:0];               // no filler bits anywhere
  199.     break;
  200.   default:
  201.     fprintf(stderr, "GraphicsWrap: attempted to create bitmap for unsupported \
  202. pixel depth. Bye!\n");
  203.     exit(1);
  204.   }    
  205.   [self initBitmap];              // initialize instance variables &
  206.                                   // clear data
  207.   return self;
  208. }
  209.  
  210. - initWithSize:(NXSize *) aSize andDepth:(int) aDepth
  211. {
  212.   [self initWithSize:aSize depth:aDepth
  213.    andColor:NXConvertRGBToColor(0.0, 0.0, 0.0)];
  214.   return self;
  215. }
  216.  
  217. // erases the current frame to aColor
  218. - eraseFrameToColor:(NXColor) aColor
  219. {
  220.   [self setBackColor:aColor];
  221.   [self eraseFrame];
  222.   return self;
  223. }
  224.  
  225. // erases the current frame to backColor
  226. - eraseFrame
  227. {
  228.   int i;
  229.   unsigned char *top_line;
  230.   
  231.   // erase first line to back color
  232.   for(i=0;i<[self pixelsWide];i++)
  233.     [self erasePoint:i:0];
  234.   
  235.   switch(imageDepth){
  236.   case NX_TwoBitGrayDepth:
  237.     top_line=&data[xyto2index(0,0)];
  238.     for(i=0;i<[self pixelsHigh];i++)
  239.       bcopy(top_line, &(data[xyto2index(0,i)]), bytes_per_row);
  240.     break;
  241.   case NX_TwelveBitRGBDepth:
  242.     top_line=&data[xyto12index(0,0)];
  243.     for(i=0;i<[self pixelsHigh];i++)
  244.       bcopy(top_line, &(data[xyto12index(0,i)]), bytes_per_row);
  245.     break;
  246.   case NX_TwentyFourBitRGBDepth:
  247.     top_line=&data[xyto24index(0,0)];
  248.     for(i=0;i<[self pixelsHigh];i++)
  249.       bcopy(top_line, &(data[xyto24index(0,i)]), bytes_per_row);
  250.     break;
  251.   }
  252.   return self;
  253. }
  254.  
  255. - plotPoint:(long)x :(long)y
  256. {
  257.   long index;
  258.  
  259.   if(x<0 || x>=[self pixelsWide] || y<0 || y>=[self pixelsHigh]) {
  260.     fprintf(stderr, "Coordinate out of bound: %d,%d\n", x, y);
  261.     return self;
  262.   }
  263.   
  264.   switch(imageDepth){
  265.   case NX_TwentyFourBitRGBDepth: 
  266.     index=xyto24index(x,y);
  267.     data[index+RED24]=cur_red;
  268.     data[index+GRN24]=cur_grn;
  269.     data[index+BLU24]=cur_blu;
  270.     break;
  271.   case NX_TwelveBitRGBDepth:
  272.     index=xyto12index(x,y);
  273.     // these only work because of the bit munging done in setColor
  274.     // RED
  275.     data[index]=
  276.       // if x is odd
  277.       (x & 0x01) ?
  278.     // set the bottom 4 bits of index to the top 4 bits of
  279.     // the current red in a most peculiar fashion
  280.     ((cur_red >> 4) | (data[index] & 0xf0)) :
  281.       // else, x is even
  282.       // set the top 4 bits of index to the top 4 bits of red
  283.       (cur_red | (data[index] & 0x0f));
  284.  
  285.     // GREEN
  286.     // if x is odd
  287.     if (x & 0x01)
  288.       data[index+1]=
  289.     // set the top 4 bits of (index+1) to the top 4 bits of
  290.     // the current green in an even more peculiar fashion
  291.     (cur_grn | (data[index+1] & 0x0f));
  292.     else 
  293.       data[index]=
  294.     // set the bottom 4 bits of (index) to the top 4 bits of
  295.     // the current green
  296.     ((cur_grn >> 4) | (data[index] & 0xf0));
  297.  
  298.     // BLUE
  299.     data[index+1]=
  300.       (x & 0x01) ?
  301.     // set the bottom 4 bits of (index+1) to the top 4 bits of
  302.     // the current blue
  303.     ((cur_blu >> 4) | (data[index+1] & 0xf0)) :
  304.       // else, x is even and we need to set the top 4 bits of (index+1)
  305.       // to the top 4 bits of the current blue
  306.       (cur_blu | (data[index+1] & 0x0f));
  307.     break;
  308.   case NX_TwoBitGrayDepth:
  309.     index=xyto2index(x,y);
  310.     switch(x%4){
  311.       // 63 is binary 00111111
  312.     case 0:data[index]=(data[index] & 63) | gray_level;
  313.       break;
  314.       // 207 is binary 11001111
  315.     case 1:data[index]=(data[index] & 207) | (gray_level>>2);
  316.       break;
  317.       // 243 is binary 11110011
  318.     case 2:data[index]=(data[index] & 243) | (gray_level>>4);
  319.       break;
  320.       // 252 is binary 11111100
  321.     case 3:data[index]=(data[index] & 252) | (gray_level>>6);
  322.       break;
  323.     }
  324.   }
  325.   return self;
  326. }
  327.  
  328. - erasePoint:(long)x :(long)y
  329. {
  330.   long index;
  331.  
  332.   if(x<0 || x>=[self pixelsWide] || y<0 || y>=[self pixelsHigh]) {
  333.     fprintf(stderr, "Coordinate out of bound: %d,%d\n", x, y);
  334.     return self;
  335.   }
  336.  
  337.   switch(imageDepth){
  338.   case NX_TwentyFourBitRGBDepth: 
  339.     index=xyto24index(x,y);
  340.     data[index+RED24]=bck_red;
  341.     data[index+GRN24]=bck_grn;
  342.     data[index+BLU24]=bck_blu;
  343.     break;
  344.   case NX_TwelveBitRGBDepth:
  345.     index=xyto12index(x,y);
  346.     // these only work because of the bit munging done in setColor
  347.     // RED
  348.     data[index]=
  349.       // if x is odd
  350.       (x & 0x01) ?
  351.     // set the bottom 4 bits of index to the top 4 bits of
  352.     // the current red in a most peculiar fashion
  353.     ((bck_red >> 4) | (data[index] & 0xf0)) :
  354.       // else, x is even
  355.       // set the top 4 bits of index to the top 4 bits of red
  356.       (bck_red | (data[index] & 0x0f));
  357.  
  358.     // GREEN
  359.     // if x is odd
  360.     if (x & 0x01)
  361.       data[index+1]=
  362.     // set the top 4 bits of (index+1) to the top 4 bits of
  363.     // the current green in an even more peculiar fashion
  364.     (bck_grn | (data[index+1] & 0x0f));
  365.     else 
  366.       data[index]=
  367.     // set the bottom 4 bits of (index) to the top 4 bits of
  368.     // the current green
  369.     ((bck_grn >> 4) | (data[index] & 0xf0));
  370.  
  371.     // BLUE
  372.     data[index+1]=
  373.       (x & 0x01) ?
  374.     // set the bottom 4 bits of (index+1) to the top 4 bits of
  375.     // the current blue
  376.     ((bck_blu >> 4) | (data[index+1] & 0xf0)) :
  377.       // else, x is even and we need to set the top 4 bits of (index+1)
  378.       // to the top 4 bits of the current blue
  379.       (bck_blu | (data[index+1] & 0x0f));
  380.     break;
  381.   case NX_TwoBitGrayDepth:
  382.     index=xyto2index(x,y);
  383.     switch(x%4){
  384.       // 63 is binary 00111111
  385.     case 0:data[index]=(data[index] & 63) | bck_gray_level;
  386.       break;
  387.       // 207 is binary 11001111
  388.     case 1:data[index]=(data[index] & 207) | (bck_gray_level>>2);
  389.       break;
  390.       // 243 is binary 11110011
  391.     case 2:data[index]=(data[index] & 243) | (bck_gray_level>>4);
  392.       break;
  393.       // 252 is binary 11111100
  394.     case 3:data[index]=(data[index] & 252) | (bck_gray_level>>6);
  395.       break;
  396.     }
  397.   }
  398.   return self;
  399. }
  400.  
  401. - setColor:(NXColor)aColor
  402. {
  403.   float red,green,blue,gray;
  404.   int r,g,b;
  405.   NXConvertColorToRGB(aColor, &red, &green, &blue);
  406.   r=floattobyte(red); g=floattobyte(green); b=floattobyte(blue);
  407.  
  408.   foreColor=aColor;
  409.   switch(imageDepth){
  410.   case NX_TwelveBitRGBDepth:
  411.     // strip bottom four bits off all colors since they are not used
  412.     // speeds up the point plotting stuff
  413.     cur_red=r & 0xf0;
  414.     cur_grn=g & 0xf0;
  415.     cur_blu=b & 0xf0;
  416.     break;
  417.   case NX_TwentyFourBitRGBDepth:
  418.     cur_red=r; cur_grn=g; cur_blu=b;
  419.     break;
  420.   case NX_TwoBitGrayDepth:
  421.     NXConvertColorToGray(aColor, &gray);
  422.     gray_level=floattobyte(gray) & 0xc0;
  423.     break;
  424.   }
  425.     return self;
  426. }
  427.  
  428. - setBackColor:(NXColor)aColor
  429. {
  430.   float red,green,blue,gray;
  431.   int r,g,b;
  432.   NXConvertColorToRGB(aColor, &red, &green, &blue);
  433.   r=floattobyte(red); g=floattobyte(green); b=floattobyte(blue);
  434.  
  435.   backColor=aColor;
  436.   switch(imageDepth){
  437.   case NX_TwelveBitRGBDepth:
  438.     // strip bottom four bits off all colors since they are not used
  439.     // speeds up the point plotting stuff by eliminating this
  440.     // operation from the plotPoint/erasePoint routines.
  441.     bck_red=r & 0xf0;
  442.     bck_grn=g & 0xf0;
  443.     bck_blu=b & 0xf0;
  444.     break;
  445.   case NX_TwentyFourBitRGBDepth:
  446.     bck_red=r; bck_grn=g; bck_blu=b;
  447.     break;
  448.   case NX_TwoBitGrayDepth:
  449.     NXConvertColorToGray(aColor, &gray);
  450.     bck_gray_level=floattobyte(gray) & 0xc0;
  451.     break;
  452.   }
  453.   [self eraseFrame];
  454.   return self;
  455. }
  456.  
  457. - (NXColor)color
  458. {
  459.   return foreColor;
  460. }
  461.  
  462. -(NXColor)backColor
  463. {
  464.   return backColor;
  465. }
  466.  
  467. - (int)imageDepth
  468. {
  469.   return imageDepth;
  470. }
  471.  
  472. // modelled after the routine on page 78 of _Computer Graphics:
  473. //   Princliples and Practice
  474. // this line method actually special cases for 8 quadrants for the
  475. // line.  By doing this, the line ALWAYS starts at x0,y0 to x1,y1.  This
  476. // is a GOOD THING when doing patterns and such that need to flow from
  477. // the start point to the end point only.
  478. // QUADRANTS:  1|2
  479. //             -+-
  480. //             3|4
  481. // Each quadrant is divided into halves at the 45 degree mark.
  482. int curX, curY;
  483.  
  484. - line:(int)x0 :(int)y0 :(int)x1 :(int)y1
  485. {
  486.   long dx, dy, incD, incDD, d, x, y;
  487.   long xadd, yadd;
  488.   dx=ABS(x1-x0); dy=ABS(y1-y0);
  489.  
  490.   if(x0>x1) {
  491.     if(y0>y1) {
  492.       // down and to the left
  493.       xadd=-1; yadd=-1;
  494.     } else {
  495.       // up and to the left
  496.       xadd=-1; yadd=1;
  497.     }
  498.   } else {
  499.     if(y0>y1) {
  500.       xadd=1; yadd=-1;
  501.     } else {
  502.       xadd=1; yadd=1;
  503.     }
  504.   }
  505.   x=x0; y=y0;
  506.   [self plotPoint:x :y];
  507.  
  508.   if(dx<dy){
  509.     d=2*dx-dy;
  510.     incD=2*dx;
  511.     incDD=2*(dx-dy);
  512.     while(y!=y1){
  513.       if(d<=0) d+=incD; else {
  514.     d+=incDD; x+=xadd;
  515.       }
  516.       y+=yadd;
  517.       [self plotPoint:x :y];
  518.     }
  519.   } else {
  520.     d=2*dy-dx;
  521.     incD=2*dy;
  522.     incDD=2*(dy-dx);
  523.     while(x!=x1){
  524.       if (d<=0) d+=incD; else {
  525.     d+=incDD; y+=yadd;
  526.       }
  527.       x+=xadd;
  528.       [self plotPoint:x :y];
  529.     }
  530.   }
  531.   
  532.   return self;
  533. }
  534.  
  535. // TGIF commands
  536. - cmdDraw:(int)x :(int)y
  537. {
  538.   [self line:curX :curY :x :y];
  539.   [self cmdMove:x :y];
  540.   return self;
  541. }
  542. - cmdMove:(int)x :(int)y
  543. {
  544.   curX=x; curY=y; return self;
  545. }
  546.  
  547. - cmdCircle:(int)r
  548. {
  549.   // draw circle of radius r at current cursor location
  550.   return self;
  551. }
  552.  
  553. - cmdFps:(int)f
  554. {
  555.   // set frames per second
  556.   return self;
  557. }
  558.  
  559. - cmdHold:(int)seconds
  560. {
  561.   // set the hold value
  562.   return self;
  563. }
  564.  
  565. - cmdNewframe
  566. {
  567.   // hold for hold value and erase the image
  568.   [self eraseFrame];
  569.   return self;
  570. }
  571.  
  572. typedef struct _ETelem {
  573.   int xmin, ymax, xmax;    // only need these coordinates. ymin is curLine.
  574.   // xmax is only used for right-edge collision detection.
  575.   int num, den, inc; // state variables of integer line calculation
  576.   int xinc;
  577.   BOOL leftEdge;     // left or right edge-- approximation direction.
  578.   struct _ETelem *next;
  579. } ETelem;
  580.  
  581. void addtoedgetable(ETelem **etable, ETelem *edge, int curLine)
  582. {
  583.   ETelem *list;
  584.   // if nothing on this scan line yet, add edge to this line.
  585.   if(!etable[curLine]) etable[curLine]=edge;
  586.   else {
  587.     // something on this line.  Deal.
  588.     if(edge->xmin < etable[curLine]->xmin) {
  589.       // add as first element
  590.       edge->next=etable[curLine];
  591.       etable[curLine]=edge;
  592.     } else {
  593.       // traverse list at the current ymin
  594.       list=etable[curLine];
  595.       while(list->next && (list->next->xmin < edge->xmin))
  596.     list=list->next;
  597.       edge->next=list->next;
  598.       list->next=edge;
  599.     }
  600.   }
  601. }
  602.  
  603. - cmdDrawPoly:vertexList
  604. {
  605.   ETelem **etable, *edge;
  606.   int s, e, numVerts, count, i, j;
  607.   id  sV, eV;
  608.   int sX=0, sY, eX, eY;
  609.   ETelem *aet=(ETelem *)nil, *list, *aeTmp, *array[256];
  610.   int curLine=0, topLine=0;
  611.   BOOL drawing=NO;
  612.  
  613.   if (!([[vertexList removeObjectAt:0] isMemberOf:[CmdBgnpoly class]])){
  614.     fprintf(stderr, "Polygon rejected:  No bgnpoly command found.\n");
  615.     return nil;
  616.   }
  617.   if (!([[vertexList removeLastObject] isMemberOf:[CmdEndpoly class]])){
  618.     fprintf(stderr, "Polygon rejected:  No endpoly command found.\n");
  619.     return nil;
  620.   }
  621.   
  622.   // allocate edgetable-- currently allocated to be the number of scanlines
  623.   // in the entire image.  Ineffecient use of memory.
  624.   etable=(ETelem **) malloc(sizeof(ETelem *) * [self pixelsHigh]);
  625.   // set pointers to null
  626.   bzero(etable, sizeof(ETelem *)*[self pixelsHigh]);
  627.  
  628.   // fill edge table
  629.   for(numVerts=[vertexList count],s=0,e=1;s<numVerts;s++, e++){
  630.     if(e==numVerts) e=0; // last vertice is end to beginning
  631.     sV=[vertexList objectAt:s];
  632.     eV=[vertexList objectAt:e];
  633.     sX=[sV x]; sY=[sV y]; eX=[eV x]; eY=[eV y];
  634.  
  635.     edge=(ETelem *) malloc(sizeof(ETelem));
  636.     edge->next=(ETelem *)nil;
  637.     if(sY<eY){
  638.       edge->xmin=sX; edge->ymax=eY;
  639.       edge->xmax=eX;
  640.       edge->num=eX-sX;
  641.       edge->den=eY-sY;
  642.       if (eY>topLine) topLine=eY;
  643.       curLine=sY;
  644.     } else {
  645.       edge->xmin=eX; edge->ymax=sY;
  646.       edge->xmax=sX;
  647.       edge->num=sX-eX;
  648.       edge->den=sY-eY;
  649.       if (sY>topLine) topLine=sY;
  650.       curLine=eY;
  651.     }
  652.     edge->inc=edge->den;
  653.     if (edge->num > 0) edge->xinc=1; else edge->xinc=-1;
  654.     addtoedgetable(etable, edge, curLine);
  655.   }
  656.  
  657.   // build AET and process
  658.   curLine=0;
  659.   aet=(ETelem *)nil;
  660.   // traverse to first scanline w/a vertex (no sense walking through everything
  661.                      // before there is anything to
  662.                      // process)
  663.   while(!etable[curLine])curLine++;
  664.  
  665.   while(curLine<=topLine) {
  666.     // add this scan-lines vertices to the AET (if any)
  667.     if(etable[curLine]){
  668.       if(!aet) aet=etable[curLine];
  669.       else {
  670.     // add to the end of the current AET
  671.     aeTmp=aet;
  672.     while(aeTmp && aeTmp->next) aeTmp=aeTmp->next;
  673.     aeTmp->next=etable[curLine];
  674.       }
  675.     }
  676.     // and sort the AET
  677.     count=0;
  678.     aeTmp=aet;
  679.     array[count++]=aeTmp;
  680.     // convert the linked list into an array to do the sort
  681.     // because the programmer hates sorting algorithms w/a passion
  682.     // and would rather use a pre-written one from K&R
  683.     while(aeTmp && aeTmp->next) { aeTmp=aeTmp->next; array[count++]=aeTmp; }
  684.     for(i=1; i<count; i++){
  685.       aeTmp=array[i];
  686.       for(j=i-1; (j>=0) && (array[j]->xmin > aeTmp->xmin); j--)
  687.     array[j+1] = array[j];
  688.       array[j+1]=aeTmp;
  689.     }
  690.     aet=array[0];
  691.     for(i=1;i<count;i++){
  692.       array[i-1]->next=array[i];
  693.     }
  694.     if(array[count-1]) array[count-1]->next=(ETelem *)nil;
  695.     array[count]=(ETelem *)nil;
  696.  
  697.     // fill pixels.
  698.     drawing=NO;
  699.     for(aeTmp=aet; aeTmp; aeTmp=aeTmp->next){
  700.       // avoid ymax==curLines points-- they do not count. (3.3)
  701.       if(aeTmp->ymax>curLine)
  702.     if(drawing){
  703.       // draw span
  704.       [self line:sX :curLine :aeTmp->xmin :curLine];
  705. #ifdef DEBUG
  706.       fprintf(stderr,"Span: %d %d %d %d\n", sX, curLine,
  707.           aeTmp->xmin, curLine);
  708. #endif
  709.       // toggle flag
  710.       drawing=NO;
  711.       aeTmp->leftEdge=NO; // this is a right edge
  712.     } else {
  713.       // starting new span-- set start x
  714.       sX=aeTmp->xmin;
  715.       // toggle flag
  716.       drawing=YES;
  717.       aeTmp->leftEdge=YES; // this is a left edge
  718.     }
  719.     }    
  720.  
  721.     // remove y=ymax
  722.     // strip from the head, if needed
  723.     while(aet && aet->ymax==curLine) {
  724.       aeTmp=aet;
  725.       aet=aet->next;
  726.       free(aeTmp);
  727.     }
  728.     list=aet;
  729.     while(list && list->next){
  730.       if(list->next->ymax==curLine)
  731.     // cut out the edge
  732.     list->next=list->next->next;
  733.       list=list->next;
  734.     }
  735.     
  736.     // update the yvalue
  737.     curLine++;
  738.     
  739.     // update the xmin values on all edges that are left
  740.     for(list=aet; list; list=list->next){
  741.       // ignore vertical lines
  742.       if(list->den){
  743.     // increase the numerator
  744.     list->inc+=ABS(list->num);
  745.     while(list->inc > list->den){
  746.       list->xmin+=list->xinc;
  747.       list->inc-=list->den;
  748.     }
  749.       }
  750.       if((list->xmax == list->xmin) && !list->inc) list->xmin-=1;
  751.     }
  752.   }
  753.   return self;
  754. }
  755.  
  756. @end
  757.